'''
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
 

示例 1：


输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：


输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''


class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        m, n = len(matrix), len(matrix[0])
        # 第一步：先找到target所在行 记每行的第一个数组成的列表为 [a[0],...,a[m-1]]
        # 先二分搜索找到 a[i]<=target<a[i+1] i=max{k |target>=a[k]}
        l, r = 0, m - 1
        while l < r:
            mid = (l + r + 1) // 2
            if target >= matrix[mid][0]:  # 去搜寻看 k 大一点是否仍满足target>=matrix[k][0]
                l = mid
            else:  # target<matrix[mid][0] 需要更小的k使target>=matrix[k][0]满足
                r = mid - 1
        row = l
        # 第二步: 找到 matrix[l][i]<=target<matrix[l][i+1] '<','<='也行 为了和前面一致
        l, r = 0, n - 1
        while l < r:
            mid = (l + r + 1) // 2
            if target >= matrix[row][mid]:  # 去搜寻看 k 大一点是否仍满足target>=matrix[k][0]
                l = mid
            else:  # target<matrix[mid][0] 需要更小的k使target>=matrix[k][0]满足
                r = mid - 1
        return matrix[row][l] == target



matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
target = 11
Solution().searchMatrix(matrix,target)